Find-first-set logic circuits and methods are used in a variety of applications to determine the first valid entry in an input data set. For example, find first-set logic circuits and methods may be used to find the first available identifier of identifiers that are managed out of order, determine an available tag for a transaction, allocate an available entry in a register file, or find the first event in a snapshot of events.
Some implementations determine the first bit having a logic 1 value in an input word. The least significant or rightmost bit that has a logic 1 value may be considered to be the first valid entry. However, current approaches may be problematic, because significant delay may be introduced into the logic path for large entry counts. That is, as the number of bits in the input data word increases, the delay introduced in finding the first set bit may exceed acceptable limits.
It is desirable to provide circuits and/or methods that address this issue.